Methods of performing compression by assigning compression codes to character information such as characters and words, using compression algorithms such as Huffman encoding and LZ78, have been known. In a compression process based on such compression algorithms, process of preparing a list of character information to which compression codes have been assigned, searching the list using character information matching the character information which is a compression target, and generating compressed data using compression codes associated with the character information obtained as a result of searching.
Searching of the list performed in the compression process described above is performed by matching between character information in the list and character information of a compression target, and as a result of matching, character information in the list matching the character information of the compression target are specified. Before performing matching with the character information in the list, the range of the matching target in the list may be narrowed using an index prepared in advance.
Further, in the compression process described above, data of a tree structure may be used for searching for character information to which a compression code is associated. For example, a Huffman tree is used in Huffman encoding, and a Trie tree is used in LZ78. With respect to conventional technologies, see Japanese Laid-open Patent Publication No. 2012-142024, and Japanese Laid-open Patent Publication No. 05-224878, for example.
Searching the list of character information, to which compression codes have been assigned by the method described above, is performed by matching between the character information in the list and character information of a compression target. As a result of matching, if they do not match, matching is performed again on the next character information in the list. If matching between units of character information is performed many times, the amount of processing for searching increases.
In particular, in the case where a compression code is not assigned to character information of a processing target in the first place, character information matching the character information of the compression target is not found. Nonetheless, if search processing is performed on character information to which a compression code is not assigned, as character information matching the character information of the compression target is not found, matching will be performed many times, whereby the processing amount of search processing increases.